// PhoneNumber.cpp : Defines the entry point for the console application.
//
/*
Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

*/

#include "stdafx.h"
#include <string>
#include <vector>
using namespace std;

char Pad[10][4]= {{' '},
            {},
            {'a','b','c'},
            {'d','e','f'},
            {'g','h','i'},
            {'j','k','l'},
            {'m','n','o'},
            {'p','q','r','s'},
            {'t','u','v'},
            {'w','x','y','z'}};
int PadCount[10] ={1, 0, 3, 3, 3, 3, 3, 4, 3, 4};

class Solution {
public:

    
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> ret;
        if(digits.size()==0) return ret;
        
        string combi;
		int pos = 0;
        
        CalculateStringRet(digits, combi, pos, ret);
        
        return ret;
        
    }
    
    bool CalculateStringRet(string digits, string& combi, int& pos, vector<string>& R)
    {
        if(pos == digits.size())
        {
            R.push_back(combi);
            return true;
        }
        
        if( digits[pos]>'9' || digits[pos]<'0' )
        {
    		return false;;
    	}
        
        int n = digits[pos] - '0';
        
        for(int i = 0; i< PadCount[n]; i++)
        {
			string ori = combi;
			combi+= Pad[n][i];
            if(!CalculateStringRet(digits, combi, ++pos, R))
                return false;
			pos--;
			combi = ori;
        }
        
        return true;
        
    }
    
 

};

int _tmain(int argc, _TCHAR* argv[])
{
	Solution S;
	S.letterCombinations("2");
	return 0;
}

